#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 024. 两两交换链表中的节点.py
@time: 2022/2/17 1:04
@desc: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
> 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
（奇偶交换）
1. 迭代
2. t: O(n), s: O(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        if not head.next: return head
        p, q, prev = head, head.next, None
        new_head = q
        while True:
            next = q.next
            q.next = p
            if prev: prev.next = q
            p.next = next
            prev = p
            p = next
            if not next or not next.next: break
            q = next.next
        return new_head

# Definition for singly-linked list.
# class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# 思路更清晰的写法
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        dummyHead = ListNode()
        dummyHead.next = head
        p = dummyHead
        while p.next and p.next.next:
            node1 = p.next
            node2 = p.next.next
            p.next = node2
            node1.next = node2.next
            node2.next = node1
            p = node1
        return dummyHead.next